﻿#include<iostream>
//#include<utility>
#include<map>
//#include<set>
using namespace std;

//int main()
//{
//	//默认去重+升序排序
//	set<int> s;//默认构造
//	//set<int, greater<int>> s;//降序
//
//	set<int> s1{ 2,4,3,1,5 };//初始化列表
//	set<int> s2(s1.begin(), s1.end());//迭代器区间构造
//	set<int> s3(s1);//拷贝构造
//	s = s1;//赋值
//
//	return 0;
//}

//int main()
//{
//	set<int> s{ 2,4,3,1,5 };
//
//	//正向遍历
//	set<int>::iterator it = s.begin();
//	while (it != s.end())
//	{
//		cout << *it << " ";
//		++it;
//	}
//	cout << endl;
//
//	//反向遍历
//	set<int>::reverse_iterator rit = s.rbegin();
//	while (rit != s.rend())
//	{
//		cout << *rit << " ";
//		++rit;
//	}
//	cout << endl;
//
//	//范围for
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	return 0;
//}

//int main()
//{
//	set<int> s;
//	s.insert(2);//直接插入
//	s.insert(2);
//	s.insert(3);
//	s.insert(1);
//	s.insert(5);
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	s.insert(s.begin(), 10);//迭代器位置插入
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	set<int> s1{ 6,7,8,9 };
//	s.insert(s1.begin(), s1.end());//迭代区间插入
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	s.insert({ 20,30,40 });//初始化列表插入
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	//直接删除x
//	int x;
//	cin >> x;
//	int num = s.erase(x);
//	if (num == 0)
//	{
//		cout << x << "不存在" << endl;
//	}
//
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	//直接查找再利用迭代器删除x
//	cin >> x;
//	auto pos = s.find(x);
//	if (pos != s.end())
//	{
//		s.erase(pos);
//	}
//	else
//	{
//		cout << x << "不存在" << endl;
//	}
//
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	return 0;
//}



//int main()
//{
//	set<int> s{ 2,3,1,5,4 };
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	int x;
//	cin >> x;
//
//	//算法库的查找 O(N)
//	auto pos1 = find(s.begin(), s.end(), x);
//
//	//set自身实现的查找 O(logN) 效率相当之快
//	auto pos2 = s.find(x);
//
//	//利用cout间接实现快速查找
//	if (s.count(x))
//	{
//		cout << x << "存在" << endl;
//	}
//	else
//	{
//		cout << x << "不存在" << endl;
//	}
//
//	cout << endl;
//
//	set<int> s1;
//	for (int i = 1; i < 10; i++)
//	{
//		s1.insert(i * 10);
//	}
//
//	for (auto e : s1)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	//[25,55]的值
//	auto itlow = s1.lower_bound(25);//返回>=25
//	auto itup = s1.upper_bound(55);//返回>55
//	
//	//删除这段区间的值
//	s1.erase(itlow, itup);
//	for (auto e : s1)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	return 0;
//}

//int main()
//{
//	//相⽐set不同的是，multiset是排序，但是不去重
//	multiset<int> s = { 2,2,2,5,1,3 };
//
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	//相⽐set不同的是，x可能会存在多个，find查找中序的第⼀个
//	int x;
//	cout << "输入x:";
//	cin >> x;
//	auto pos = s.find(x);
//	while (pos != s.end() && *pos == x)
//	{
//		cout << *pos << " ";
//		++pos;
//	}
//	cout << endl;
//
//	//相⽐set不同的是，count会返回x的实际个数
//	cout << s.count(x) << endl;
//
//	//相⽐set不同的是，erase时会删除所有的x 
//	s.erase(x);
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	return 0;
//}


//int main()
//{
//	pair<string, int> p1;
//	pair<string, int> p2("apple", 5);
//	pair<string, int> p3(p2);
//	p1 = make_pair("pear", 10);
//	p3 = p2;
//
//	cout << p1.first << ":" << p1.second << endl;
//	cout << p2.first << ":" << p2.second << endl;
//	cout << p3.first << ":" << p3.second << endl;
//
//	return 0;
//}

//int main()
//{
//	map<string, string> dict;//无参默认构造
//	map<string, string> dict1 = { {"left","左边"}, {"right", "右边"}, {"insert", "插入"},{ "string", "字符串" } };//初始化列表构造
//	map<string, string> dict2(dict1);//拷贝构造
//	map<string, string> dict3(dict1.begin(), dict1.end());//迭代器区间构造
//	dict = dict1;//赋值重载
//
//	return 0;
//}


//int main()
//{
//	map<string, string> dict = { {"left","左边"}, {"right", "右边"}, {"insert", "插入"},{ "string", "字符串" } };
//
//	//正向遍历
//	map<string, string>::iterator it = dict.begin();
//	while (it != dict.end())
//	{
//		cout << (*it).first << ":" << (*it).second << endl;
//		++it;
//	}
//	cout << endl;
//
//	//范围for
//	for (auto e : dict)
//	{
//		cout << e.first << ":" << e.second << endl;
//	}
//
//	return 0;
//}


//int main()
//{
//	//insert
//	map<string, string> dict;
//
//	pair<string, string> kv1("first", "第一个");
//	dict.insert(kv1);//插入显示pair对象
//
//	dict.insert(pair<string, string>("second", "第二个"));//插入匿名pair对象
//
//	dict.insert(make_pair("sort", "排序"));//插入make_pair函数
//
//	//C++11：初始化列表
//	dict.insert({ "auto", "自动的" });
//
//	//注：插入相等key，value不会更新
//	dict.insert({ "auto","自动的xxxx" });
//
//	//可以修改value，不支持修改key
//	map<string, string>::iterator it = dict.begin();
//	//it->first += 'y';  //err
//	it->second += 'y';
//
//	while(it!=dict.end())
//	{
//		cout << it->first << ":" << it->second << endl;
//		++it;
//	}
//	cout << endl;
//
//	//erase
//	dict.erase("sort");//直接删除key
//	dict.erase(dict.begin());//删除迭代器位置的key
//
//	for (auto e : dict)
//	{
//		cout << e.first << ":" << e.second << endl;
//	}
//
//
//	//[]
//	map<string, string> dict1;
//	dict1.insert({ "sort","排序" });
//
//	dict1["insert"];//key不存在->插入
//	dict1["left"] = "左边";//key不存在->插入+修改
//	dict1["left"] = "左边xxx";//key存在->修改
//
//	//查找时如果key不存在，那么就会变成插入
//	cout << dict1["right"] << endl;
//
//	for (auto e : dict1)
//	{
//		cout << e.first << ":" << e.second << endl;
//	}
//
//	return 0;
//}



//int main()
//{
//	map<char, int> dict;
//	dict['a'] = 5;
//	dict['b'] = 10;
//	dict['c'] = 15;
//	dict['d'] = 20;
//
//	map<char, int>::iterator it = dict.find('a');//find
//	cout << it->first << ":" << it->second << endl;
//
//	cout << dict.count('b') << endl;//count
//
//	cout << endl;
//
//	//['a','b']
//	map<char, int>::iterator low = dict.lower_bound('a');//>='a'
//	map<char, int>::iterator up = dict.upper_bound('b');//>'b'
//	dict.erase(low, up);//删除['a','b']区间
//
//	for (auto e : dict)
//	{
//		cout << e.first << ":" << e.second << endl;
//	}
//
//	return 0;
//}


//void test1()
//{
//	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };
//	map<string, int> countMap;
//
//	//先查找⽔果在不在map中
//	//1、不在，说明⽔果第⼀次出现，则插⼊{⽔果, 1}
//	//2、在，则查找到的节点中⽔果对应的次数++
//	for (const auto& str : arr)
//	{
//		map<string, int>::iterator ret = countMap.find(str);
//		if (ret == countMap.end())
//		{
//			countMap.insert({ str,1 });
//		}
//		else
//		{
//			ret->second++;
//		}
//	}
//
//	for (const auto& e : countMap)
//	{
//		cout << e.first << ":" << e.second << endl;
//	}
//}
//
//
//
//void test2()
//{
//	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };
//	map<string, int> countMap;
//
//	// []先查找⽔果在不在map中
//    // 1、不在，说明⽔果第⼀次出现，则插⼊{⽔果, 0}，同时返回次数的引用，++一下就变成1次了
//    // 2、在，则返回⽔果对应的次数++
//	for (const auto& str : arr)
//	{
//		countMap[str]++;//插入+修改
//	}
//
//	for (const auto& e : countMap)
//	{
//		cout << e.first << ":" << e.second << endl;
//	}
//}
//
//
//void test3()
//{
//	map<string, string> dict;
//
//
//}
//int main()
//{
//	test1();
//	cout << endl;
//	test2();
//	return 0;
//}